package com.template.tree;

/**
 * 二叉查找树（Binary Search Tree，BST）
 *
 * 1 对于每个节点，它的左子树中所有节点的值小于它的值，右子树中所有节点的值大于它的值。
 * 2 每个节点都要唯一地标识，即不能有重复的节点。
 * 3 左右子树也分别满足上述两个条件，因此可以递归地定义 BST。
 *
 * 因为 BST 的这些特性，对于一个具有 n 个节点的 BST，可以进行许多高效的操作，例如查找、插入和删除等，时间复杂度为 O (log n)。
 *
 * 但需要注意的是，如果 BST 退化成了一条链（即所有节点都只有一个子节点），则删除的时间复杂度为 O (n)，这是因为它就变成了普通的链表。
 * @author shenb
 * @date 2023-03-28 14:59
 */
public class BSTree {
    private Node root; // BST 的根节点

    // 节点定义
    private static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    // 插入节点
    public void insert(int value) {
        root = insert(root, value);
    }

    private Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }
        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }
        return node;
    }

    // 查找节点
    public boolean contains(int value) {
        return contains(root, value);
    }

    private boolean contains(Node node, int value) {
        if (node == null) {
            return false;
        }
        if (value < node.value) {
            return contains(node.left, value);
        } else if (value > node.value) {
            return contains(node.right, value);
        } else {
            return true;
        }
    }

    // 删除节点
    public void delete(int value) {
        root = delete(root, value);
    }

    private Node delete(Node node, int value) {
        if (node == null) {
            return null;
        }
        if (value < node.value) {
            node.left = delete(node.left, value);
        } else if (value > node.value) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                Node minRight = node.right;
                while (minRight.left != null) {     // 从当前节点右子树中向左遍历，找到最小的节点
                    minRight = minRight.left;
                }
                node.value = minRight.value;         // 将右子树最小节点的值赋给当前节点，作为根节点
                node.right = delete(node.right, minRight.value);    // 在右子树中删除最小节点
            }
        }
        return node;
    }
}
